輸入：一個由 0/1 組成的 numpy grid（0 = 路, 1 = 牆）。

起點/終點：例如左上 (1,1) 到右下 (H-2, W-2)。

演算法：

BFS：保證最短路徑（在單位步長迷宮中）。

A*：用啟發式（曼哈頓距離）加速搜尋。

紀錄：

所有展開節點（便於分析）。

轉折點（路徑中方向改變的節點）。

分岔點（鄰居可走 > 2 的節點）。

死路（鄰居可走 ≤ 1 且不是起點/終點的節點）。

捷徑（比較 BFS 與 A* 走的路徑，找出有差異的地方）。

import heapq

def get_neighbors(grid, x, y):
H, W = grid.shape
dirs = [(1,0),(-1,0),(0,1),(0,-1)]
res = []
for dx,dy in dirs:
nx,ny = x+dx, y+dy
if 0 <= nx < W and 0 <= ny < H and grid[ny,nx]==0:
res.append((nx,ny))
return res

def bfs_shortest_path(grid, start, goal):
from collections import deque
queue = deque([start])
visited = {start: None} # parent
while queue:
cur = queue.popleft()
if cur == goal:
break
for nb in get_neighbors(grid,*cur):
if nb not in visited:
visited[nb] = cur
queue.append(nb)
# reconstruct path
path = []
node = goal
while node is not None:
path.append(node)
node = visited.get(node)
return path[::-1], visited

def astar_shortest_path(grid, start, goal):
def h(n): # heuristic: Manhattan distance
return abs(n[0]-goal[0]) + abs(n[1]-goal[1])
open_set = [(h(start), 0, start, None)] # (f, g, node, parent)
came_from = {}
gscore = {start:0}
while open_set:
_, g, node, parent = heapq.heappop(open_set)
if node in came_from:
continue
came_from[node] = parent
if node == goal:
break
for nb in get_neighbors(grid,*node):
ng = g+1
if nb not in gscore or ng < gscore[nb]:
gscore[nb]=ng
heapq.heappush(open_set, (ng+h(nb), ng, nb, node))
# reconstruct path
path=[]
node = goal
while node is not None:
path.append(node)
node = came_from.get(node)
return path[::-1], came_from

--- 分析函式 ---

def analyze_path(grid, path):
H,W = grid.shape
turns=[]
branches=[]
deadends=[]
for i,(x,y) in enumerate(path):
nbs = get_neighbors(grid,x,y)
if len(nbs) > 2:
branches.append((x,y))
if len(nbs) <= 1 and (i not in (0,len(path)-1)):
deadends.append((x,y))
if 0<i<len(path)-1:
dx1,dy1 = path[i][0]-path[i-1][0], path[i][1]-path[i-1][1]
dx2,dy2 = path[i+1][0]-path[i][0], path[i+1][1]-path[i][1]
if (dx1,dy1)!=(dx2,dy2):
turns.append((x,y))
return {
"turns": turns,
"branches": branches,
"deadends": deadends
}

--- 測試 ---

W,H = 21,21
maze = dfs_maze(W,H, seed=7)
start, goal = (1,1), (W-2,H-2)

bfs_path, bfs_visit = bfs_shortest_path(maze,start,goal)
astar_path, astar_visit = astar_shortest_path(maze,start,goal)

bfs_info = analyze_path(maze,bfs_path)
astar_info = analyze_path(maze,astar_path)

print("BFS 最短路徑長度:", len(bfs_path))
print("A* 最短路徑長度:", len(astar_path))
print("轉折點:", bfs_info["turns"])
print("分岔點:", bfs_info["branches"])
print("死路:", bfs_info["deadends"])